1. Technical Field
This invention relates to knowledge-based systems, and more particularly to a knowledge-based system which combines case-based reasoning, heuristic search, and deductive rule application.
2. Discussion
Knowledge-based systems, such as expert systems, have specialized problem-solving capabilities utilizing the knowledge that underlines human expertise. The field of knowledge engineering is concerned with developing new principles, tools and techniques for utilizing the knowledge of human experts in problem-solving. Knowledge-based methods and systems are useful in many important tasks which do not have tractable algorithmic solutions, such as planning, legal reasoning, medical diagnosis, geological exploration, and military situation analysis. These problems originate in complex social or physical contexts, and generally resist precise description and rigorous analysis.
Current knowledge-based systems generally fall into the category of rule-based or case-based reasoning. In either approach, an important goal is to make the reasoning sensitive to the context of the problem. Both approaches have shortcomings which prevent the realization of this goal. In more detail, current rule-based technology utilizes deductive inference from antecedents to conclusions. One problem with this approach is its inflexibility. For example, in rule-based expert systems, this often leads to one of two problems during knowledge acquisition: 1) antecedents of rules are too specific, which leads to systems that are not broad enough and require additional knowledge acquisition to add more rules, and 2) antecedents that are too general leading to an inability to decide which rules to apply and requiring extra knowledge acquisition to acquire control rules which are difficult for a domain expert to explicate and difficult to maintain once the system has been built. In brief, the current rule-based reasoning approaches are limited to strict, deductive rule application. Two examples of state of the art rule application technologies are the PROLOG compilation (see Warren, D. H. 1977, "Implementing Prologue: Compiling Predicate Login Programs" (DAI Research Papers Nos. 39 & 40) Department of Artificial Intelligence, University of Edinburgh) and the Rete Network Compilation (see Forgy C. L. (1982), Rete: "A Fast Algorithm For The Many Pattern/Many Object Pattern-Matching Problem", Artificial Intelligence, 19(1), 17-37).
Nevertheless, as different approaches have been attempted to increase context sensitivity, the efficiency has decreased. In addition to rules which can be learned from an expert, a knowledge engineer must invent a new set of rules (such as control rules) used to sequence through the knowledge. These rules do not relate to the way the expert solves the problem, instead they are concerned with getting the knowledge applied in the right order. For example, one approach would be to first find out from an expert when a rule applies and then use a set of rules which determines when a set of rules apply. Also, when a given rule does apply the system must sequence to another set of rules which apply when those rules apply.
Case-based reasoning methods are generally classified into two types: 1) domain independent, feature-based approaches and 2) domain dependent knowledge-based approaches. Domain independent approaches are easy to apply because all one needs are a set of cases and a case matcher. In these approaches, indexing of case memory allows efficient access but representations are limited to flat features only and is inappropriate for problems requiring structured representations. Flat features are numbers or strings, for which matching metrics are easy and computationally inexpensive. Structured representation specify relationships between features for which matching metrics are difficult to define and computationally expensive. A representative domain independent approach is found Goodman, M. (1989), "CBR in Battle Planning", In Case-based Reasoning Workshop, (pp. 264-269), Morgan Kaufman.
In contrast, domain dependent approaches utilize inference rules to help match cases. In domain dependent approaches, special indexing strategies must be created for each new application. This makes the application much more expensive and difficult to maintain. A representative domain dependent approach is described in Bareiss, R. Porter, B. W., and Murray, K.S. (1989), "Supporting Start-To-Finish Development of Knowledge Bases", Machine Learning, Vol. 4, (3/4), 259-284.
Thus, it would be desirable to provide a knowledge-based system which is both context-sensitive and efficient. Further, it would be desirable to provide a knowledge-based system which avoids the necessity of the control rules required in rule-based expert systems Also, it would be desirable to provide a knowledge-based system which can utilize the advantages of both case-based and rule-based reasoning while minimizing their respective disadvantages. Further, it would be desirable to provide a knowledge-based system in which the cases used are not limited to flat features but can contain structural features. Further, it would be desirable to provide a knowledge-based system which simplifies the knowledge acquisition process.